// 一个机器人位于一个 m x n 网格的左上角。

// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
// 问总共有多少条不同的路径？

const uniquePaths = function (m: number, n: number): number {
    const dp: number[] = new Array(m).fill(1);// 申请一列的动态规划空间
    // 这里留意行和列都是从1开始遍历
    for (let col = 1; col < n; col++) {
        for (let row = 1; row < m; row++) {
            dp[row] += dp[row - 1];// 状态转移方程
        }
    }
    // 返回最后的dp计算值
    return dp[dp.length - 1];
};


// 这道题也是一道经典的动态规划例题
// 如果知道思路的话并不困难，其实就是我们可以在矩阵方格里面模拟填数
// 可以发现当前格子的方法总数，其实只与其上方和右方的路径总和有关
// 于是可以想到使用动态规划算法来解决，比较直观的是申请一个m × n的矩阵空间
// 然后将第一行第一列初始化为1，然后递推剩余的所有位置
// 但是在递推的过程中其实会发现我们实际在计算的过程中只用到了1列的数据
// 故我们还可以进一步对申请的矩阵空间进行压缩，减小空间复杂度。